const nodeType = {
  name: 'title', // 节点名称
  children: [], // 子节点
};

const root = {
  name: 'Top',
  children: [
    {
      name: 'Level 1',
      children: [
        {
          name: 'Level 1-1',
          children: [],
        },
        {
          name: 'Level 1-2',
          children: [],
        },
      ],
    },
    {
      name: 'Level 2',
      children: [
        {
          name: 'Level 2-1',
          children: [],
        },
        {
          name: 'Level 2-2',
          children: [],
        },
      ],
    },
  ],
};

{
  // 深度优先遍历
  // 树结构的深度优先遍历（DFS）
  // 从后端拿到一个文档节点树结构，请按照深度优先遍历的顺序，返回该树结构的所有节点名称
  // 输出下面的结果
  [
    'Top',
    'Level 1',
    'Level 1-1',
    'Level 1-2',
    'Level 2',
    'Level 2-1',
    'Level 2-2',
  ];
  const deepDFS = (root, nodeList) => {
    if (root) {
      nodeList.push(root.name);
      // 递归root.children，找root的子节点
      root.children && root.children.forEach((v) => deepDFS(v, nodeList));
    }
    return nodeList;

    // 下面这个不是很好理解，可以理解为和koa洋葱模型一样，从外向内，然后再从内向外执行
    // if (!root) return [];
    // const newList = [];
    // newList.push(root.name);
    // root.children && root.children.forEach((v) => newList.push(...deepDFS(v)));
    // return newList;
  };
  console.time('DFS-start');
  console.log(deepDFS(root, []));
  console.timeEnd('DFS-start');
  // const deepDFS = (root) => {
  //   const res = [];
  //   function dfs(root) {
  //     if (root) {
  //       res.push(root.name);
  //       root.children && root.children.forEach((child) => dfs(child));
  //     }
  //   }
  //   dfs(root);
  //   return res;
  // };
}

{
  // 广度优先遍历
  // 树结构的广度优先遍历（BFS）
  // 从后端拿到一个文档节点树结构，请按照广度优先遍历的顺序，返回该树结构的所有节点名称
  // 输出下面的结果
  [
    'Top',
    'Level 1',
    'Level 2',
    'Level 1-1',
    'Level 1-2',
    'Level 2-1',
    'Level 2-2',
  ];

  // 广度优先遍历
  const deepBFS = (root, nodeList = []) => {
    const queue = [root];
    // 循环判断队列的长度是否大于0
    while (queue.length > 0) {
      // 取出队列添加的节点
      const p = queue.shift();
      nodeList.push(p.name);
      // 根据节点是否含有children,如果有子节点则添加到队列中
      p.children && p.children.forEach((v) => queue.push(v));
    }
    return nodeList;
  };
  console.time('BFS-start');
  console.log(deepBFS(root, []));
  console.timeEnd('BFS-start');
}

// 经过测试发现：
// 广度优先遍历的时间明显比深度优先的时间效率要高
// 广度优先遍历是用队列来记录每一个节点的位置，所以会占用内存更多点，
// 深度优先遍历是从根节点往子节点递归查询，当子节点查询完了，就从根节点的兄弟节点依次往下搜索所以比较耗时，
// 所以搜索效率上广度优先遍历更高
